| 翻訳と辞書 |
| unknotting problem ： ウィキペディア英語版 |
unknotting problem
In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms. A major unresolved challenge is to determine if the problem admits a polynomial time algorithm, that is, whether the problem lies in the complexity class P.
==Computational complexity==
First steps toward determining the computational complexity were undertaken in proving that the problem is
in larger complexity classes, which contain the class P. By using normal surfaces to describe the Seifert surfaces of a given knot, showed that the unknotting problem is in the complexity class NP. claimed that the problem of testing whether a knot has genus at least ''k'' (for a given number ''k'') is in NP; this would imply that unknotting is in NP ∩ co-NP, but remains unpublished. claimed the weaker result that unknotting is in AM ∩ co-AM; however, later they retracted this claim.〔Mentioned as a "personal communication" in reference () of .〕 In 2011, Greg Kuperberg proved that (assuming the generalized Riemann hypothesis) the unknotting problem is in co-NP.〔.〕
The unknotting problem has the same computational complexity as testing whether an embedding of an undirected graph in Euclidean space is linkless.〔.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「unknotting problem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|